/**
 * @file streamsummarybucket_ptr.cpp
 * @brief Implementation of Stream-Summary datastructure using map of buckets.
 * @author Andreas Bok Andersen
 *
 * */
#include <boost/range/adaptor/map.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <boost/foreach.hpp>
#include <boost/assign.hpp>

#ifndef ENTRY
#include "entry.h"
#endif

#include "bucket3.h"

typedef pair<int, Bucket2*> INT_BUCKET_REF_PAIR;
typedef pair<size_t, Bucket2*> ENTRY_HASH_BUCKET_REF_PAIR;
typedef unordered_map<int, Bucket2*> INT_BUCKET2_REF_MAP;
typedef unordered_map<size_t, Bucket2*> ENTRY_HASH_BUCKET_REF_MAP;

typedef unordered_map<int, Bucket2> INT_BUCKET2_MAP;
#define STREAMSUMMARYBUCKET

class StreamSummaryBucket: public Summary::Summary {
private:
	ENTRY_HASH_BUCKET_REF_MAP * entries;
	INT_BUCKET2_REF_MAP * buckets;

	Bucket2* min_bucket;
	void add_item(int i, int j, float w);
	void increase(int i, int j, float w);
	void replace_min(int i, int j, float w);

public:
	StreamSummaryBucket(int k) :
			Summary::Summary(k) {
		this->min_bucket = NULL;
		this->entries = new ENTRY_HASH_BUCKET_REF_MAP();
		this->buckets = new INT_BUCKET2_REF_MAP();
	}

	~StreamSummaryBucket() {
		INT_BUCKET2_REF_MAP::iterator it;
		for (it = buckets->begin(); it != buckets->end(); it++) {
			delete it->second;
		}
		delete entries;
		delete buckets;
		//cerr << "destructor SSH" << endl;
	}

	void insert(int i, int j, float w) {
		//printf("\n(%d,%d,%.3f)\n", i, j, w);
		if (this->entries->find(hash_value(i, j)) != entries->end()) {
			//cerr << "INCREASE" << endl;
			this->increase(i, j, w);
		} else if (this->entries->size() < this->k) {
			//cerr << "ADD" << endl;
			this->add_item(i, j, w);
		} else {
			//cerr << "REPLACE" << endl;
			replace_min(i, j, w);
		}
		//cerr << this->to_string() << endl;
	}

	ENTRY_VEC get_summary();
	void get_summary(ENTRY_VEC * summary);
	void get_summary(Entry summary[]);

	bool checksummary() {
		Bucket2 *b = min_bucket;
		assert(b->prev == NULL);
		while (b->next) {
			assert(b->key < b->next->key);
			if (b->prev != NULL)
				assert(b->key > b->prev->key);
			b = b->next;
			assert(b->key > b->prev->key);
		}
	}

	string to_string() {
		stringstream ss;
		Bucket2 *b = min_bucket;
		ss << b->to_string() << " -> ";
		while (b->next) {
			b = b->next;
			ss << b->to_string() << " -> ";
		}
		return ss.str();
	}

	Entry * get_min_el();

	int summarysize() {
		return this->entries->size();
	}
};

/**
 * Adds element to summary
 * @param i,j index of row
 * @param w value of A[i,j]
 */
void StreamSummaryBucket::add_item(int i, int j, float w) {
	/*
	 * get new key
	 * make new entry
	 * get pointer
	 * New bucket
	 * if min == NULL :
	 * 		insert mew bucket
	 * 		add entry to bucket
	 * 		add entry to entries
	 * 		set min bucket
	 * */

	int key = (int) ceil(w);
	Entry * e = new Entry(i, j, w, 0.0);
	Bucket2 * b;
	if (this->min_bucket == NULL) {
		b = new Bucket2(key, NULL, NULL);
		b->add(e);
		this->buckets->insert(INT_BUCKET_REF_PAIR(key, b));
		this->entries->insert(ENTRY_HASH_BUCKET_REF_PAIR(e->hash, b));
		this->min_bucket = b;
	} else if (this->buckets->find(key) == this->buckets->end()) {
		/*
		 * find insertion point
		 * insert new bucket
		 * add element to bucket
		 * update next
		 * add entry -> bucket mapping
		 *
		 * */
		Bucket2 *_bucket = min_bucket;
		while (_bucket->next && (_bucket->next->key < key)) {
			_bucket = _bucket->next;
		}
		b = new Bucket2(key, _bucket, NULL);
		b->add(e);

		this->buckets->insert(INT_BUCKET_REF_PAIR(key, b));
		if (_bucket->next) {
			b->next = _bucket->next;
			_bucket->next->prev = b;
		}
		_bucket->next = b;
		this->entries->insert(ENTRY_HASH_BUCKET_REF_PAIR(e->hash, b));

	} else {
		/*
		 * insert entry into bucket
		 * add mapping
		 * */
		b = this->buckets->find(key)->second;
		b->add(e);
		this->entries->insert(ENTRY_HASH_BUCKET_REF_PAIR(e->hash, b));
	}

}
/**
 * Increases value of existing item in summary
 */
void StreamSummaryBucket::increase(int i, int j, float w) {
	/*
	 * get entry
	 * get curr_bucket
	 * get new key
	 * init Bucket2*
	 *
	 * if has new key:
	 * 		if (new key != curr_key :
	 * 			update entry mapping
	 * 			add entry to existing bucket
	 * 			remove from curr_bucket
	 *
	 * */
	//cerr << this->to_string() << endl;
	size_t e_hash = hash_value(i, j);
	Bucket2 * curr_bucket = this->entries->find(e_hash)->second;
	//cerr << "curr " << (*curr_bucket).to_string() << endl;
	Entry * e = curr_bucket->elements.find(e_hash)->second;
	e->weight = w + e->weight;
	int _key = (int) ceil(e->weight);
	Bucket2 * bucket;
	if (this->buckets->find(_key) != this->buckets->end()) {
		if (curr_bucket->key != _key) {
			// new key exists && new key != curr key
			if (curr_bucket->elements.size() == 1) {
				//cerr << "new key exists && new key != curr key" << endl;
				/* Only element  "e" in curr_bucket. Update bucket key
				 * Remove mapping in buckets for curr_key -> bucket
				 * Update key for current bucket
				 */
				this->buckets->erase(curr_bucket->key);
				this->entries->find(e_hash)->second =
						this->buckets->find(_key)->second;
				this->buckets->find(_key)->second->add(e);
				curr_bucket->remove(e);
				if (curr_bucket == this->min_bucket) {
					this->min_bucket = curr_bucket->next;
					this->min_bucket->prev = NULL;
				} else {
					if (curr_bucket->next) {
						curr_bucket->next->prev = curr_bucket->prev;
					}
					curr_bucket->prev->next = curr_bucket->next;

				}
				delete curr_bucket;

			} else {
				//cerr << "new key exists && new key == curr key" << endl;
				this->entries->find(e_hash)->second =
						this->buckets->find(_key)->second;
				this->buckets->find(_key)->second->add(e);
				curr_bucket->remove(e);
			}
		}
	} else {
		Bucket2 *_bucket = curr_bucket;
		while (_bucket->next && (_bucket->next->key < _key)) {
			_bucket = _bucket->next;
		}
		//printf("new key !exists. curr.size %d, currkey %d, _bucket.key %d", curr_bucket->elements.size(), curr_bucket->key, _bucket->key);

		if (curr_bucket->elements.size() == 1) {
			//cerr << "new key == curr key && curr_bucket.elements.size== 1" << endl;
			// insertion point == curr_bucket and contains only element e -> update key of curr
			this->buckets->erase(curr_bucket->key);
			curr_bucket->key = _key;
			this->buckets->insert(
					INT_BUCKET_REF_PAIR(curr_bucket->key, curr_bucket));
			this->entries->find(e_hash)->second =
					this->buckets->find(_key)->second;
		} else {
			//bucket = new Bucket2(_key, _bucket, NULL);
			//cerr << "new key != curr key " << endl;
			bucket = new Bucket2(_key, _bucket, _bucket->next);
			bucket->add(e);
			this->buckets->insert(INT_BUCKET_REF_PAIR(_key, bucket));
			//cerr << this->to_string() << endl;
			if (_bucket->next) {
				_bucket->next->prev = bucket;
				//bucket->next = _bucket->next;
			}
			//cerr << this->to_string() << endl;
			_bucket->next = bucket;
			this->entries->find(e->hash)->second = bucket;
			curr_bucket->remove(e);
			//cerr << this->to_string() << endl;
		}
	}
}

/**
 * @return Returns element with minimum value
 */
Entry * StreamSummaryBucket::get_min_el() {
	/*HASH_ENTRY_REF_MAP::iterator it = this->min_bucket->elements.begin();
	 Entry * min_el = it->second;
	 for (; it != this->min_bucket->elements.end(); it++) {
	 if (it->second->weight < min_el->weight)
	 min_el = it->second;
	 }
	 return min_el;*/
	return this->min_bucket->elements.begin()->second;
}

/**
 * Replaces minimum element with a new item.
 */
void StreamSummaryBucket::replace_min(int i, int j, float w) {
	//Entry * min = get_min_el();
	Entry * min = this->min_bucket->elements.begin()->second;
	//cerr << "found min" << min->to_string() << endl;
	min->eps = min->weight;
	min->weight += w;

	int key = (int) ceil(min->weight);
	//printf ("new key: %d\n", key);
	Bucket2 * bucket;
	if (this->buckets->find(key) != this->buckets->end()) {
		//printf("new key exists\n");
		bucket = this->buckets->find(key)->second;
		this->min_bucket->remove(min);
		this->entries->erase(min->hash);
		min->i = i;
		min->j = j;

		min->hash = hash_value(i, j); // rehash on swapped item
		bucket->add(min);
		this->entries->insert(ENTRY_HASH_BUCKET_REF_PAIR(min->hash, bucket));

		//delete min;
		if (!this->min_bucket->has_elements()) {
			bucket = this->min_bucket;
			this->min_bucket = this->min_bucket->next;
			this->min_bucket->prev = NULL;
			this->buckets->erase(bucket->key);
			delete bucket;
		}

		//cerr << "new key exists" << endl;
	} else {
		//cerr << "!new key exists" << endl;
		Bucket2 * _bucket = this->min_bucket;

		while (_bucket->next && (_bucket->next->key < key)) {
			_bucket = _bucket->next;
		}
		if (this->min_bucket->elements.size() == 1) {
			if (_bucket == this->min_bucket) {
				this->buckets->erase(this->min_bucket->key);
				this->min_bucket->remove(min);
				this->entries->erase(min->hash);

				this->min_bucket->key = key; // update key
				this->buckets->insert(
						INT_BUCKET_REF_PAIR(this->min_bucket->key,
								this->min_bucket));
				min->i = i;
				min->j = j;
				min->hash = hash_value(i, j); // rehash on swapped item
				this->min_bucket->add(min);
				this->entries->insert(
						ENTRY_HASH_BUCKET_REF_PAIR(min->hash,
								this->min_bucket));
			} else {
				bucket = this->min_bucket;
				this->min_bucket = this->min_bucket->next;
				this->buckets->erase(bucket->key);
				bucket->remove(min);
				this->entries->erase(min->hash);

				bucket->key = key; // update key
				bucket->prev = _bucket;
				bucket->next = _bucket->next;
				if (_bucket->next) {
					_bucket->next->prev = bucket;
				}
				_bucket->next = bucket;
				this->buckets->insert(INT_BUCKET_REF_PAIR(bucket->key, bucket));

				min->i = i;
				min->j = j;
				min->hash = hash_value(i, j); // rehash on swapped item
				bucket->add(min);
				this->entries->insert(
						ENTRY_HASH_BUCKET_REF_PAIR(min->hash, bucket));
			}
		} else {
			bucket = new Bucket2(key, _bucket, _bucket->next);
			this->buckets->insert(INT_BUCKET_REF_PAIR(key, bucket));
			this->min_bucket->remove(min);
			this->entries->erase(min->hash);

			if (_bucket->next) {
				_bucket->next->prev = bucket;

			}
			_bucket->next = bucket;
			min->i = i;
			min->j = j;
			min->hash = hash_value(i, j); // rehash on swapped item

			bucket->add(min);
			this->entries->insert(ENTRY_HASH_BUCKET_REF_PAIR(min->hash, bucket));
		}
	}
}

/**
 * Fill entries into vector of Entry. Argument is passed by reference
 * @param entries pointer to vector<Entry>
 */
void StreamSummaryBucket::get_summary(ENTRY_VEC *summary) {
	Bucket2 * min = min_bucket;
	HASH_ENTRY_REF_MAP::iterator it;
	while (min != NULL) {
		for (it = min->elements.begin(); it != min->elements.end(); it++) {
			summary->push_back(*it->second);
		}
		min = min->next;
	}
}
/**
 * Fill entries into array of Entry. Argument is passed by reference
 * @param entries[] pointer to array of Entry
 */
void StreamSummaryBucket::get_summary(Entry *summary) {
	Bucket2 *min = min_bucket;
	HASH_ENTRY_REF_MAP::iterator it;
	int i = 0;
	while (min != NULL) {
		for (it = min->elements.begin(); it != min->elements.end(); it++) {
			summary[i] = *it->second;
			i++;
		}
		min = min->next;
	}
}
/**
 * @return Returns summary as a vector of Entry
 */
ENTRY_VEC StreamSummaryBucket::get_summary() {
	ENTRY_VEC summary;
	Bucket2 *min = min_bucket;
	HASH_ENTRY_REF_MAP::iterator it;
	while (min != NULL) {
		for (it = min->elements.begin(); it != min->elements.end(); it++) {
			summary.push_back(*it->second);
		}
		min = min->next;
	}
	return summary;
}
